package data_structure;

//https://blog.csdn.net/weixin_42089228/article/details/106094853
public class Array<AnyType>{
    private static final int DEFAULCAPACITY = 10;
    private int size;
    private AnyType[] data;

    public Array(){
        size = 0;
        ensureCapacity(DEFAULCAPACITY);
    }

    public int getSize(){
        return size;
    }

    public int getCapacity(){
        return data.length;
    }

    public void addFirst(AnyType element){
        add(0,element);
    }

    public void addLast(AnyType element){
        add(size,element);
    }

    public void add(int idx,AnyType element){
        if(size == getCapacity()){
            ensureCapacity(getCapacity()* 2);  
        }
        for(int i = size;i<idx;i--){
            data[i] = data[i-1];
        }
        data[idx] = element;
        size++;
    }

    public AnyType removeFirst(){
        return remove(0);
    }

    public AnyType removeLast(){
        return remove(size-1);
    }

    public AnyType remove(int idx) {
		if(data.length == 0 || idx >= size)
				throw new IllegalArgumentException("index 不合法");
		AnyType ret = data[idx];
		if(idx != size - 1) {
			for(int i = idx; i < size; i++) {
				data[i] = data[i+1];
			}
		}
		size--;
		if(size == getCapacity()/4 && getCapacity()/2 != 0) {
			ensureCapacity(getCapacity()/2);
		}
		return ret;
	}
	
	public boolean contains(AnyType element) {
		for(int i = 0; i < size; i++) {
			if(data[i] == element)
				return true;
		}
		return false;
	}
	
	public int find(AnyType element) {
		for(int i = 0; i < size; i++) {
			if(data[i] == element)
				return i;
		}
		return -1;
	}
	
	public AnyType get(int idx) {
		return data[idx];
	}
	
	public void delete(AnyType element) {
		int idx = find(element);
		if(idx == -1)
			return;
		remove(idx);
    }
    
	@Override
	public String toString() {
		String s = new String();
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("size:"+size+'\n');
		stringBuilder.append("capacity:"+getCapacity()+'\n');
		stringBuilder.append('[');
		for(int i = 0; i < size; i++) {
			stringBuilder.append(data[i]);
			if(i != size - 1)
				stringBuilder.append(',');
		}
		stringBuilder.append(']');
		s = stringBuilder.toString();
		return s;
	}
	
	private void ensureCapacity(int newCapacity) {
		if(newCapacity < size)
			return;
		AnyType[] old = data;
		data = (AnyType[])new Object[newCapacity];
		for(int i = 0; i < size; i++) {
			data[i] = old[i];
		}
	}	
    public static void main(String[] args) {
        Array<Integer> biao = new Array<Integer>();
        biao.addFirst(1);
        biao.addFirst(2);
        biao.addFirst(3);
        biao.addFirst(4);
        biao.addFirst(5);
        biao.addFirst(6);
        biao.addFirst(7);
        biao.addFirst(8);
        biao.addFirst(9);
        biao.addFirst(10);
        System.out.println(biao.find(4));
        biao.delete(5);
        System.out.println(biao.find(5));
        System.out.println("hello world");
    }
}